#define _CRT_SECURE_NO_WARNINGS 1
#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
    int LIS(vector<int>& a)
    {
        int n = a.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        int max = 0;
        for (int i = n - 1;i >= 0;i--)
        {
            for (int j = i;j < n;j++)
            {
                if (i == j) dp[i][j] = 1;
                else if (j - i == 1)
                {
                    if (a[j] > a[i]) dp[i][j] = 1;
                    else dp[i][j] = 0;
                }
                else
                {
                    int tmp = dp[i + 1][j - 1];
                    if (a[i] < a[i + 1]) ++tmp;
                    if (a[j] > a[j - 1]) ++tmp;
                    dp[i][j] = tmp;
                }
                if (dp[i][j] > max) max = dp[i][j];
            }
        }
        for (auto a : dp)
        {
            for (auto b : a)
            {
                cout << b << " ";
            }
            cout << endl;
        }
        return max;
    }
};